/**
 * 八皇后问题的递归解法
 */

#include <stdio.h>

#define CHESS_WIDTH 8
int chess[CHESS_WIDTH];
int sol_cnt;

int is_place_ok(int* a, int n, int c)
{
    for (int i = 0; i < n; i++) 
    {
        if (a[i] == c || a[i] - i == c - n || a[i] + i == c + n)
        {
            return 0;
        }
    } 
    return 1;
}

void add_queen(int* a, int n)
{
    if (n >= CHESS_WIDTH)
    {
        puts("\n");
        puts("########################");
        for (int i = 0; i < CHESS_WIDTH; i++)
        {
            for (int j = 0; j < CHESS_WIDTH; j++)
            {
                if (chess[i] == j) 
                {
                    printf("1 ");
                } else
                {
                    printf("0 ");
                }
            }
            printf("\n");
        }
        puts("########################");
        sol_cnt++;
        return;
    }
    for (int i = 0; i < CHESS_WIDTH; i ++)
    {
        if (is_place_ok(a, n, i))
        {
            a[n] = i;
            add_queen(a, n + 1);
        }
    }
}

int main(void)
{
    add_queen(chess, 0);
    printf("find solutions:%d\n", sol_cnt);
    return 0;
}